package 牛客.字符串;/*
 *@Author: helen
 *@Date:   2021/4/25 9:00
 *@Description:
 题目描述
    给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，
    请输出将str1编辑成str2的最小代价。
    示例1
        输入   "abc","adc",5,3,2
        返回值  2
    示例2
        输入   "abc","adc",5,3,100
        返回值  8
 */


public class 最小编辑代价 {
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        if(str1 == null && str2 == null)
            return 0;
        int len1 = str1.length();
        int len2 = str2.length();
        if(len1 == 0)
            return ic*len2;
        if(len2 == 0)
            return dc*len1;
        int [][] dp = new int[len1 + 1][len2 + 1];
        //初始化dp的第一行和第一列
        for (int i = 0; i <= len2; i++) {
            dp[0][i] = ic*i;
        }
        for (int j = 0; j <= len1; j++) {
            dp[j][0] = dc*j;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if(str1.charAt(i - 1) == str2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = dp[i - 1][j - 1] + rc;
                //取三种情况的最小值
                dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic);
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc);
            }
        }
        return dp[len1][len2];
    }

    public static void main(String[] args) {
        最小编辑代价 obj = new 最小编辑代价();
        String str1 = "abc";
        String str2 = "adc";
        final int i = obj.minEditCost(str1, str2, 5, 3, 100);
        System.out.println(i);
    }
}
